Typically, a switch has two parts; a switching network or switching fabric and a control. The switching network interconnects a set of input lines with a set of output lines. More particularly, the switching network serves to provide a plurality of simultaneous message paths or circuit connections. Each message path or circuit connection connects a particular input line with a particular output line. The control serves to set-up and tear down particular message paths.
When an individual circuit connection or message path is dedicated for the duration of a message, circuit switching is said to take place. However, when the message can be represented by a bursty data stream, a technique called packet switching may be employed. In this case, the incoming data is formed into packets of a defined length. An individual circuit connection or message path within the switching network lasts only for the duration of each packet. Thus, each packet belonging to a particular message follows an associated "virtual circuit". As will be seen below, the distinction between circuit switching and packet switching may be blurred in particular systems.
In general, circuit switching may be classified in accordance with the manner by which data passes through the switching network contained in the circuit switch. In space division switches the message paths in the switching network are separated in space. In time division switches the message paths in the switching network are separated in time, (i.e., time multiplexing is used). Some circuit switches are characterized by both space division and time division.
Most space division switches currently in use in telephone systems comprise one or more stages of coordinate switching networks. A coordinate switching network is a matrix array of cross points, metallic contacts, or electronic devices, etc. by which several inputs can be separately and simultaneously connected to several outputs. The number of cross points required in a coordinate switching network increases quadratically with an increase in the number of input lines or an increase in the number of output lines.
To reduce the number of crosspoints per simultaneous message path, space division switches are constructed with several stages of coordinate switching network and connecting links between stages. If a message path cannot be established because suitable connecting links or outputs are not available, "blocking" is said to occur. Specifically, given an idle input and an idle output but no available internal connecting link, the condition is defined to be "matching loss". Multistage networks are designed to provide an acceptably low probability of matching loss. If the probability of matching loss is zero, the network is said to be non-blocking.
In a time division switch, the switching network is time multiplexed. The input signal stream received on each input line includes signals from multiple messages in a time multiplexed format, a representation typically digital, of each message appearing in a periodically recurring interval of time called a time-slot. In other words, the input signal stream at each input comprises frames which are subdivided into slots. The switching network in a time division switch is generally synchronous. Slots are simultaneously transmitted through the switching network from particular inputs to particular outputs. The message paths or circuit connections in the switching network are reconfigured for each time slot period so that data arriving at the same input in successive time slots may be routed to different outputs.
Each input line to the switching network in the time division switch may include an associated input time-slot interchanger. Similarly, each output line from the switching network in the time division switch also includes an associated output time-slot interchanger. Arriving time-slots in a particular frame are written into an input time-slot interchanger in the sequence of their arrival and read out of the time-slot interchanger for transmission through the switching network in a different sequence. The time-slot interchangers are needed to avoid blocking problems, when time-slots simultaneously arrive at two inputs destined for the same output. In this case, the time-slot interchanger associated with one of the inputs rearranges the order of its time-slots.
Examples of time division circuit switches which include one or more stages of coordinate switching networks are the No. 4ESS and the No. 5ESS of AT&T. In the 4ESS and 5ESS the settings of the cross points in the switching networks are reconfigured at a rate of millions of times per second. The settings of these cross points are usually determined by the content of one or more control RAMS, which in turn are written by a central controller.
One alternative to a matrix type switching network, in which the settings of the cross points are controlled by RAMs, is a self-routing switching network. In a self-routing switching network, routing control is accomplished by attaching a header in front of each information block or data packet to be routed through the network. The header contains the address of the outgoing line to which the information block is to be routed. The address enables the switching nodes in the self-routing switching network to make their own routing decisions. In other words, each header serves to establish a connection between an input and a desired output. These connections may be dynamically reconfigured by changing the headers. An example of a self-routing switching network is the well known Batcher-Banyan network which comprises a Batcher sorting network followed by a Banyan routing network.
Self-routing switching networks have been used to provide communications among processors and memory modules in a computer network, and such self-routing switching networks have also been used in a packet switch. (See for example Huang, et al. U.S. Pat. No. 4,516,238, and Huang et al. Starlite: A Wideband Digital Switch, Copyright 1984 IEEE).
An object of the present invention is to provide a time division circuit switch which is based on a self-routing switching network. More particularly, it is an object of the present invention to provide a circuit switch utilizing a self-routing switching network, which switch serves as a cross connect for DS3 signals and other signals comprising frames organized into slots.